package 数据结构.sort;

import java.util.Arrays;

/**
 * 选择排序的推演
 * 时间复杂度 是 O(n^2);
 */
public class SelectSort {
    public static void main(String[] args) {
        int[] arr = {101, 34, 119, 1};


    }

    public static void selectSort(int[] arr) {

        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i;
            int min = arr[i];
            for (int j = 1 + i; j < arr.length; j++) {
                if (arr[i] > arr[j]) {
                    min = arr[j];
                    minIndex = j;
                }
            }
            if (minIndex != i) {
                arr[minIndex] = arr[i];
                arr[i] = min;
            }
        }
        System.out.println(Arrays.toString(arr));


        //原始数据: 101,34,119,1
        //先简单在复杂;可以把复杂的算法拆分为简单的问题在逐步的解决最后在综合
        //第一轮
       /* int minIndex = 0;
        int min = arr[0];
        for (int j = 1; j < arr.length; j++) {
            if (min > arr[j]) {//说明min不是最小值
                min = arr[j];//取到更小值
                minIndex = j;//记录下更小值的下标
            }
        }//这次循环结束,得到最小值和最小值的下标,接下来完成交换
        if (minIndex != 0) {
            arr[minIndex] = arr[0];
            arr[0] = min;
        }
        System.out.println("第一轮排序:");
        System.out.println(Arrays.toString(arr));

        //第二轮
        minIndex = 1;
        min = arr[1];
        for (int j = 2; j < arr.length; j++) {
            if (min > arr[j]) {//说明min不是最小值
                min = arr[j];//取到更小值
                minIndex = j;//记录下更小值的下标
            }
        }//这次循环结束,得到最小值和最小值的下标,接下来完成交换
        if (minIndex != 1) {
            arr[minIndex] = arr[1];
            arr[1] = min;
        }
        System.out.println("第二轮排序:");
        System.out.println(Arrays.toString(arr));


        //第三轮
        minIndex = 2;
        min = arr[2];
        for (int j = 3; j < arr.length; j++) {
            if (min > arr[j]) {//说明min不是最小值
                min = arr[j];//取到更小值
                minIndex = j;//记录下更小值的下标
            }
        }//这次循环结束,得到最小值和最小值的下标,接下来完成交换
        if (minIndex != 2) {
            arr[minIndex] = arr[2];
            arr[2] = min;
        }
        System.out.println("第三轮排序:");
        System.out.println(Arrays.toString(arr));*/
    }


}
